"""
2787. 将一个数字表示成幂的和的方案数
中等
相关标签
premium lock icon
相关企业
提示
给你两个 正 整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2^3 + 3^3 + 5^3 。



示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 3^2 + 1^2 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。
示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 4^1 = 4 。
- n = 3^1 + 1^1 = 4 。


提示：

1 <= n <= 300
1 <= x <= 5
"""


class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        # dp? 0视为一次，代表刚好等于
        dp = [1] + [0] * n
        for i in range(1,n+1):
            #当前的
            num = i ** x
            #如果大于n，后续都大于所以中断
            if num>n:
                break
            #背包，>=的数字要计算一次
            for j in range(n,num-1,-1):
                dp[j] += dp[j-num]
        return dp[n]%1_000_000_007